home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / superopt.5 / superopt / superopt-2.5 / TODO < prev    next >
Encoding:
Text File  |  1995-05-18  |  7.1 KB  |  159 lines
  1. * For the 960, we often see sequences "chkbit;concmp" where the chkbit is
  2.   just used to unconditionally clear bit 2 of Ac.cc.  We might want to prune
  3.   the variants of chkbit to decrease the number of printed sequences.
  4.  
  5. * For the 960, we pass the prune hints based on bit 1 of the Ac.cc.  This
  6.   might lead to undesirable pruning.
  7.  
  8. * For the 960 and Alpha, we let conditionally executed instructions like
  9.   ADDO_cc_960, SUBO_cc_960, and CMOVEcc overwrite an existing register.
  10.   This is OK, but we should also write to a new register, since several
  11.   conditional adds and subtracts with different conditions and the same
  12.   destination register might make the result well-defined anyway.
  13.  
  14. * When we have conditional execution (HPPA, i960, Alpha, Sparc9, Coldfire,
  15.   etc) we have to make sure we prune instruction 3 carefully in this
  16.   situation:
  17.  
  18.     insn1
  19.     insn2 is conditionally executed
  20.     insn3
  21.  
  22.   Depending on the flag settings of insn1 and insn2, the correct set of
  23.   insn3 to try is tricky.  Now, we might prune too much.
  24.  
  25. * Later 29k models have additional logical ops.  Add them!
  26.  
  27. * add_co(a,a) and shiftl_co(a,1) are identical.  Affects m68k, x86, pyr, etc.
  28.  
  29. * For goal functions with the same arity, the exact same computations are
  30.   made in synth.  This suggests that we could search for many goal functions
  31.   in parallel instead of serially.  We could maintain an array of goal
  32.   values, one for each goal.  Instead of simply comparing the last generated
  33.   value to goal_value, we would loop through a goal_values[] array, and call
  34.   test_sequence for each goal that matches.  This would speed up searches by
  35.   as much as a factor of 10.
  36.  
  37. * Adding the bsfl instruction revealed a deficiency: We can't deal with
  38.   instructions that give an undefined result for some inputs.  This is so
  39.   because the sequences might fail to work only when the undefined result
  40.   happen to become a certain value.  To cope with this, we have to make
  41.   test_sequence try lots of values, but it can only do that if it knows
  42.   about these instructions.
  43.  
  44.   A cleaner way would be to add a valid bit to each computed value.
  45.  
  46. * Now we require equality between a computed goal value and a computed
  47.   result.  Permit fuzzier function, like "something negative".  E.g., a
  48.   fuzzy sgn function might be useful.
  49.  
  50. * Most importantly: Generalize the class of possible goal functions.  Allow
  51.   them to be any mapping from a vector of words to another vector of words,
  52.   each of arbitrary length.
  53.  
  54.   To make it fast, record after each instruction if it generates a value
  55.   that is in (the vector) goal_value, and prune a sequence if it has not
  56.   produced N-M requested values when M more instructions are allowed [N the
  57.   number of words in goal_value].
  58.  
  59.   We should split `synth'.  The leaf search `synth' function could be
  60.   written like currently, but with the leaf-test "if (allowed_cost > 0)"
  61.   removed.  The non-leaf `synth' need to loop and look for the generated
  62.   value in goal_value.  To avoid massive code replication, we have to put
  63.   the synth function in a separate file, and play with cpp and #include.
  64.  
  65.   Make sure to handle the case were you find all values before the last
  66.   instruction.  This might be non-trivial!  We know that we have to use the
  67.   value from the ultimate instruction, otherwise we would have found this
  68.   sequence before.  Problem is, we will either have to loop and look for
  69.   the value in goal_value, or, probably much better, just accept the
  70.   sequence.
  71.  
  72. * Add -test-on-cpu option triggering a mechanism for testing the generated
  73.   sequences on the real hardware.  That would help debug the simulation
  74.   code.
  75.  
  76. * I'd like to have a means to define that a goal function is not defined
  77.   for all possible input values.  An extra parameter, ALLOWED_ARGUMENTS, to
  78.   DEF_GOAL could take care of that.
  79.  
  80.   Also I'd like the user to have the possibility to add a list of immediate
  81.   values to try for each goal function.  For example, 31 and 32 could be
  82.   useful for ffs.
  83.  
  84. * Make it possible to handle more immediate values, for example by putting
  85.   them in the immediate_val array.
  86.  
  87. * Interpret goal functions so the user doesn't need to recompile.
  88.   Interpretation would make goal function evaluation slower than it is now,
  89.   but goal function evaluation is not critical.
  90.  
  91. * Add code to algebraically prove that generated sequences are correct.
  92.  
  93. * Add bsrl/bsfl and bfffo to CISC synth.
  94.  
  95. * Check that PERFORM_CLZ works like RS/6000's cntlz and 29k's clz.  Is it
  96.   ok for input == 0?
  97.  
  98. * A major speed improvement would be to make independent insn have a
  99.   canonical order.  Consider `gts' on the SPARC.  This is probably not very
  100.   hard, if insns are enumerated in some clever way and loop variables are
  101.   passed down.  A very simple but potentially quite powerful mechanism: If
  102.   the putative instruction doesn't depend on the last instruction, compare
  103.   the putative instruction's opcode with the last instruction's opcode, and
  104.   proceed iff, say, the < relation holds.
  105.  
  106.   After an instruction that sets carry (and there is another instruction
  107.   with the same effect apart from that it doesn't affect carry), the
  108.   generated carry has to be used.  [Fix this with a reservation vector
  109.   --allow both making and deleting a reservation.  Make reservation when
  110.   carry is generated and delete it when it is used.]  The leaf instructions
  111.   have to input carry if an unused carry is pending.
  112.  
  113.   Make sure all computed values are used by subsequent instructions.  For
  114.   example, if we have just two more values to compute and three yet unused
  115.   values, the last two instructions have to restrict their input operands.
  116.  
  117. * Efficient pruning of sequences not using generated resources:
  118.  
  119.   Each generated instruction should record it's computed 'resources' in a
  120.   list of unused resources.  (A written register is such a resource, and the
  121.   carry flag is such a resource.)  When a resource is used by an
  122.   instruction, it's removed from the data base.
  123.  
  124.   At each recursion, we check that the unused resources can be consumed
  125.   with the allowed number of instructions.  If not, we back-track.
  126.  
  127.   Beware: A resource is not 'consumed' when it has been used.  I have seen
  128.   optimal sequences that uses a generated carry more than once.
  129.  
  130. * Shift 32 steps on 68k is well-defined.  LSHIFTR_CO can be used to zero a
  131.   word and simultaneously move the sign bit to the X flag, ASHIFTR_CO can
  132.   be used to propagate the sign bit to the whole word and to the X flag.
  133.   Useful?
  134.  
  135. * Model the exact timing, i.e., instruction overlap, superscalar issue,
  136.   etc.  Requires modelling the CPU internal function units.
  137.  
  138. * `386: bt, clc, cmc, cdq[0->1], lea, shld, shrd, stc.
  139.  
  140. * Make the instruction description cleaner.  Something of this kind would
  141.   be great:
  142.  
  143.   88k:
  144.     {ADD,        "addu        %d{r},%1{r,0},%2{r,[0-FFFF]}"},
  145.     {ADD_CI,    "addu.ci    %d{r},%1{r,0},%2{r,[0-FFFF]}"},
  146.     ...
  147.  
  148.   sparc:
  149.     {ADD,        "add        %1{r,0},%2{r,[-1000,+FFF]},%d{r}"},
  150.     {ADD_CI,    "addx        %1{r,0},%2{r,[-1000,+FFF]},%d{r}"},
  151.     ...
  152.  
  153.   We would need a tool to extract the information and generate a 'synth'
  154.   function.  (That instruction description format would be useful to
  155.   assemblers, disassemblers, and simulators too.)
  156.  
  157. * Include a 'synth' function for several targets in one gso binary.  Have a
  158.   command line option -t<target> select which one to use.
  159.